package flare.analytics.cluster
{
  import flare.util.Arrays;
  import flare.util.Property;
  import flare.util.Sort;
  import flare.vis.data.Data;
  import flare.vis.data.DataList;
  import flare.vis.data.EdgeSprite;
  import flare.vis.data.NodeSprite;
  import flare.vis.data.Tree;
  import flare.vis.operator.Operator;

  /**
   * Base class for clustering operators that construct a hierarchical
   * clustering tree. Provides methods for taking a sequence of
   * merge operations by a clustering algorithm and constructing a
   * resulting cluster tree.
   * 
   * <p>Once a clustering has been computed, each node included in the
   * analysis will be annotated with both its cluster membership
   * using the name indicated by the <code>clusterField</code> property.
   * By default, this class will attempt to pick an optimal level of the
   * cluster tree at which to break up items into discrete clusters.
   * However, clients can invoke the <code>labelNodes</code> method with
   * a specific merge number which indicates the point at which to "cut"
   * the cluster tree into discrete sub-clusters. This class also annotates
   * nodes with a sequence number using the name indicated by the
   * <code>sequenceField</code> property. The sequence number allows items
   * to be sorted in a way that attempts to preserve the clustered structure.
   * Additionally, the <code>clusterTree</code> property will return a
   * <code>flare.vis.data.Tree</code> instance that can be used to
   * visualize the structure of the cluster tree.</p>
   */
  public class HierarchicalCluster extends Operator
  {
    /** @private */
    protected var _idx:Property = Property.$("props.sequence");
    /** @private */
    protected var _com:Property = Property.$("props.cluster");

    /** @private */
    protected var _qvals:Array;
    /** @private */
    protected var _merges:MergeEdge;
    /** @private */
    protected var _size:int;
    /** @private */
    protected var _tree:Tree;
    /** @private */
    protected var _group:String = Data.NODES;

    /** The data group to cluster. */
    public function get group():String
    {
      return _group;
    }

    public function set group(g:String):void
    {
      _group = g;
    }

    /** The property in which to store cluster indices. This property
     *  is used to annotate nodes with the community they belong to
     *  (indicated as an integer index). The default value
     *  is "props.cluster". */
    public function get clusterField():String
    {
      return _com.name;
    }

    public function set clusterField(f:String):void
    {
      _com = Property.$(f);
    }

    /** The property in which to store sequence indices. This property
     *  is used to annotate nodes with their sequence index along the
     *  computed cluster tree. This value can be used to sort the nodes
     *  in a way that best preserves community structure. The default value
     *  is "props.sequence". */
    public function get sequenceField():String
    {
      return _idx.name;
    }

    public function set sequenceField(f:String):void
    {
      _idx = Property.$(f);
    }

    /** Computed criterion values for each merge in the cluster tree. */
    public function get criteria():Array
    {
      return _qvals;
    }

    /** The cluster tree of detected community structures. The leaf nodes
     *  correspond to each of the nodes in the input graph, and include the
     *  same <code>data</code> property. Non-leaf nodes indicate merges
     *  made by the clustering algorithm, and have <code>data</code>
     *  properties that include the <code>merge</code> number (1 for the
     *  first merger, 2 for the second, etc), the <code>criterion</code>
     *  value computed for that merge, and the <code>size</code> of the
     *  cluster rooted at that node (the number of descendants in the
     *  cluster tree).
     */
    public function get clusterTree():Tree
    {
      return _tree;
    }

    // --------------------------------------------------------------------

    /**
     * Creates a new HierarchicalCluster instance. 
     */
    public function HierarchicalCluster()
    {
      super();
    }

    /**
     * Labels nodes with their cluster membership, determined by
     * the given merge number. If the merge number is less than
     * zero or unprovided, the merge number that maximizes the
     * clustering criteria will be assumed.
     * @param merge the merge number at which to compute the clusters
     */
    public function labelNodes(merge:int = - 1):void
    {
      if(merge < 0)merge = Arrays.maxIndex(_qvals);
      var com:int, idx:int;
      var helper:Function = function(n:NodeSprite):void
      {
        var nn:NodeSprite;

        if(n.childDegree && n.data.merge > merge)
        {
          for(var i:int = 0; i < n.childDegree; ++i)
          helper(n.getChildNode(i));
        }
        else if(n.childDegree)
        {
          n.visitTreeDepthFirst(function(c:NodeSprite):void
          {
            if(c.childDegree == 0)
            {
              nn = c.props.node;
              _com.setValue(nn, com);
              _idx.setValue(nn, idx++);
            }
          });
          com++;
        }

        else
        {
          nn = n.props.node;
          _com.setValue(nn, com++);
          _idx.setValue(nn, idx++);
        }
      }
      helper(_tree.root);
    }

    /**
     * @private
     * Constructs the cluster tree from the cluster results
     */
    protected function buildTree(list:DataList):Tree
    {
      var tree:Tree = new Tree();

      var e:MergeEdge, i:int, j:int, ii:int, map:Object = {
      };

      var l:NodeSprite, r:NodeSprite, p:NodeSprite;

      // populate the leaf notes
      for(i = 0; i < _size; ++i)
      {
        map[i] = (p = new NodeSprite());
        p.data = list[i].data;
        p.props.node = list[i];
        p.props.size = 0;
      }

      // build up the tree
      for(ii = 0, e = _merges.next; e != null; ++ii, e = e.next)
      {
        i = e.i;
        j = e.j;
        l = map[i];
        r = map[j];
        map[i] = (p = new NodeSprite());

        if(l.props.size >= r.props.size)
        {
          p.addChildEdge(new EdgeSprite(p, l));
          p.addChildEdge(new EdgeSprite(p, r));
        }

        else
        {
          p.addChildEdge(new EdgeSprite(p, r));
          p.addChildEdge(new EdgeSprite(p, l));
        }
        p.data.merge = ii + 1;
        p.data.criterion = _qvals[ii];
        p.props.size = 2 + l.props.size + r.props.size;
        delete map[j];
      }

      // build and sort array of cluster roots
      var roots:Array = [];

      for each(var n:NodeSprite in map)
      roots.push(n);
      roots.sort(Sort.$("-props.size"));

      // merge cluster roots into final tree, if needed
      if(roots.length == 1)
      {
        p = NodeSprite(roots[0]);
      }

      else
      {
        p = new NodeSprite();
        p.data.merge = ii;

        for each(n in roots)
        {
          p.addChildEdge(new EdgeSprite(p, n));
        }
      }
      tree.root = p;
      return tree;
    }
  } // end of class HierarchicalCluster
}